# 多变量动态规划
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        diff = [0] * n

        DP = [0] * n
        DP1 = [0] * n
        DP2 = [0] * n
        DP3 = [0] * n
        for i in range(1, n):
            diff[i] = prices[i] - prices[i - 1]
            if i == 1:
                DP1[i] = diff[1]
            else:
                if i == 2:
                    DP1[i] = max(diff[1] + diff[2], diff[2])
                    DP2[i] = DP1[i - 1]
                else:
                    DP1[i] = max(DP1[i - 1] + diff[i], DP3[i - 1] + diff[i])
                    DP2[i] = DP1[i - 1]
                    DP3[i] = max(DP2[i - 1], DP3[i - 1])
            DP[i] = max(DP1[i], DP2[i], DP3[i])
        return DP[-1]


# 单变量动态规划
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        diff = [0] * n

        DP = [0] * n
        DP1 = [0] * n
        for i in range(1, n):
            diff[i] = prices[i] - prices[i - 1]
            if i == 1:
                DP1[i] = diff[1]
                DP[i] = max(DP1[0], DP1[1])
            else:
                if i == 2:
                    DP1[i] = max(diff[1] + diff[2], diff[2])
                    DP[i] = max(DP1[0], DP1[1], DP1[2])
                else:
                    DP1[i] = max(DP1[i - 1] + diff[i], DP[i - 3] + diff[i])
                    DP[i] = max(DP1[i], DP1[i - 1], DP1[i - 2], DP[i - 3])
        return DP[-1]


data = Solution()
prices = [2, 1, 4]
print(data.maxProfit(prices))
prices = [1, 2, 4]
print(data.maxProfit(prices))
prices = [1, 2, 3, 0, 2]
print(data.maxProfit(prices))
prices = [4, 2, 1]
print(data.maxProfit(prices))
prices = [6, 1, 3, 2, 4, 7]
print(data.maxProfit(prices))
prices = [2, 1, 2, 1, 0, 1, 2]
print(data.maxProfit(prices))
prices = [4, 2, 7, 1, 11]
print(data.maxProfit(prices))
